package com.mojito.learn.algorithm.leetcode;

import com.mojito.learn.algorithm.datastructure.ListNode;
import com.mojito.learn.algorithm.datastructure.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author liufq
 * @date 2021-02-27 23:36:51
 */
public class LeetCode1 {

    /**
     * 100. 相同的树
     */
    public boolean isSameTree(TreeNode p, TreeNode q, int... method) {
        int i = method.length != 0 ? method[0] : 0;
        switch (i) {
            case 0:
                return isSameTree0(p, q);
            case 1:
                return isSameTree1(p, q);
        }
        return true;
    }

    /**
     * 方法一：深度优先遍历
     */
    private boolean isSameTree0(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    /**
     * 方法二：广度优先遍历
     */
    private boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else {
            Queue<TreeNode> queue0 = new LinkedList<>();
            Queue<TreeNode> queue1 = new LinkedList<>();
            queue0.offer(p);
            queue1.offer(q);

            while (!queue0.isEmpty() && !queue1.isEmpty()) {
                TreeNode node0 = queue0.poll();
                TreeNode node1 = queue1.poll();
                if (node0.val != node1.val) {
                    return false;
                }

                TreeNode left0 = node0.left;
                TreeNode right0 = node0.right;
                TreeNode left1 = node1.left;
                TreeNode right1 = node1.right;
                if (left0 == null ^ left1 == null) {
                    return false;
                }
                if (right0 == null ^ right1 == null) {
                    return false;
                }

                if (left0 != null) {
                    queue0.offer(left0);
                }
                if (right0 != null) {
                    queue0.offer(right0);
                }
                if (left1 != null) {
                    queue1.offer(left1);
                }
                if (right1 != null) {
                    queue1.offer(right1);
                }
            }
            return queue0.isEmpty() && queue1.isEmpty();
        }
    }

    /**
     * 101. 对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    private boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

    /**
     * 104. 二叉树的最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        return count(root) == targetSum;
    }

    private int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        return root.val + count(root.left) + count(root.right);
    }

    /**
     * 112. 路径总和
     */
//    public boolean hasPathSum(TreeNode root, int targetSum) {
//        int i = hasPathSum1(root);
//        return i == targetSum;
//    }
    private int hasPathSum1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        return root.val + hasPathSum1(root.left) + hasPathSum1(root.right);
    }

    /**
     * 118. 杨辉三角
     */
    public List<List<Integer>> generate(int numRows) {
        int[][] dp = new int[numRows][numRows];
        for (int i = 0; i < numRows; i++) {
            dp[i][i] = 1;
            dp[i][0] = 1;
        }

        for (int i = 2; i < numRows; i++) {
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> item = new ArrayList<>();
            for (int j = 0; j < numRows; j++) {
                if (dp[i][j] != 0) {
                    item.add(dp[i][j]);
                }
            }
            result.add(item);
        }

        return result;
    }

    /**
     * 119. 杨辉三角 II
     * <p>
     * 解题思路：
     * 典型的动态规划题型，先用动态规划实现，
     * 然后发现只用到了最后一行数据，不需要保存之前的数据，于是优化成滚动数组，降低空间复杂度。
     */
    public List<Integer> getRow(int rowIndex) {
        int[] val = new int[rowIndex + 1];

        for (int i = 0; i < rowIndex + 1; i++) {
            int[] temp = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    temp[j] = 1;
                } else {
                    temp[j] = val[j - 1] + val[j];
                }
            }
            val = temp;
        }

        return Arrays.stream(val).boxed().collect(Collectors.toList());
    }

    /**
     * 121. 买卖股票的最佳时机
     * 解题思路：
     * 先尝试动态规划，二维数组实现，然后发现空间复杂度很高，超出内存限制
     * 然后考虑去掉 dp 数组，使用滚动指针实现，发现只是优化了空间复杂度，时间复杂度很高，超出时间限制
     * 最后思考怎么获得最大收益，卖出的那天和历史最低价差最大的那天就是，一次遍历
     * 都是动态规划的思想，不同的实现方式
     */
    public int maxProfit(int[] prices) {
        // 历史最低价
        int min = Integer.MAX_VALUE;
        int val = 0;

        for (int price : prices) {
            min = Math.min(min, price);
            val = Math.max(val, price - min);
        }
        return val;
    }

    /**
     * 136. 只出现一次的数字
     */
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    /**
     * 141. 环形链表
     */
    public boolean hasCycle(ListNode head, int... args) {
        switch (args[0]) {
            case 0:
                return hasCycle0(head);
            case 1:
                return hasCycle1(head);
            default:
                throw new RuntimeException();
        }
    }

    /**
     * 解法一：哈希表
     */
    private boolean hasCycle0(ListNode head) {
        Set<ListNode> data = new HashSet<>();
        while (head != null) {
            if (!data.add(head)) {
                return true;
            } else {
                head = head.next;
            }
        }
        return false;
    }

    /**
     * 解法二：快慢指针
     * 慢指针每次走一步，快指针每次走两步，如果有环，快指针一定会再次和慢指针相遇
     */
    private boolean hasCycle1(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}
